package leetcode_600;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *@author 周杨
 *SubarraySumEqualsK_560 给定一个数组 判断有多少个子集相加等于k
 *describe:用数组和解决 AC 44%
 *2018年9月14日 下午2:44:27
 */
public class SubarraySumEqualsK_560 {
	
	public static void main(String[] args) {
		SubarraySumEqualsK_560 test=new SubarraySumEqualsK_560();
		/*System.out.println(test.subarraySum(new int[] {1,1,1}, 2));
		System.out.println(test.subarraySum(new int[] {-2, -1, 2, 1}, 1));
		System.out.println(test.subarraySum(new int[] {1, 0, -1}, -1));*/
		System.out.println(test.subarraySum(new int[] {1, 1, 1}, 2));
	}
	
	/**
	 * describe:用数组和 和Map解决 AC
	 * 2018年9月14日 下午3:50:30
	 */
	public int subarraySum1(int[] nums, int k) {
		 int sum = 0, result = 0;
	        Map<Integer, Integer> preSum = new HashMap<>();
	        preSum.put(0, 1);
	        
	        for (int i = 0; i < nums.length; i++) {
	            sum += nums[i];
	            if (preSum.containsKey(sum - k)) {
	                result += preSum.get(sum - k);
	            }
	            preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
	        }
	        
	        return result;
    }
	
	
	/**
	 * describe:动态规划 AC 3% 数据太多了 耗费空间
	 * 2018年9月14日 下午2:44:56
	 */
	public int subarraySum(int[] nums, int k) {
		if(nums.length==0)
			return 0;
		int dp[]=new int[nums.length];
		int res=0;
		for(int i=0;i<nums.length;++i) {
			for(int j=0;j<=i;++j) {
				dp[j]+=nums[i];
				if(dp[j]==k)
					++res;
			}
		}
		return res;
    }
}
